package edu.aa12;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

import lpsolve.*;

public class Bound {

	public static double oneTreeLB(BnBNode node, final Graph graph, Kruskal kruskal) {
		double result = 0;
		
		// get all included edges
		List<Edge> includedEdges = new ArrayList<Edge>();
		BnBNode n = node;
		while(n.parent!=null) {
			if(n.edgeIncluded) {
				result += graph.getLength(n.edge);
				includedEdges.add(n.edge);
			}
			n = n.parent;
		}
		
		// find the next #1 vertice whose incident edges can be removed (that is, they were not already included to any node)
		int nextVertice = -1;
		for (int i = 0; i < graph.vertexCoords.length; i++) {
			nextVertice = i;
			for (Edge edge : graph.incidentEdges[i]) {
				if(includedEdges.contains(edge)) {
					nextVertice = -1;
					break;
				}
			}
			if(nextVertice > -1) {
				break;
			}
		}
		
		// create a new graph, so the original one is not changed
		Graph g = new Graph(graph.vertexCoords) {
		};
		for (Edge edge : graph.edges) {
			g.createEdge(edge.u, edge.v);
		}

		if(nextVertice > -1) {
			// remove all edges from the chosen vertex
			List<Edge> incidentEdges = graph.incidentEdges[nextVertice];
			g.edges.removeAll(incidentEdges);

			// sort edges in non descending order
			List<Edge> tmp = new ArrayList<Edge>(incidentEdges);
			Collections.sort(tmp, new Comparator<Edge>() {
				public int compare(Edge o1, Edge o2) {
					return Double.compare(graph.getDistance(o1.u, o1.v),
							graph.getDistance(o2.u, o2.v));
				}
			});
			// add the two minimal edges from the chosen vertex
			result += graph.getLength(tmp.get(0)) + graph.getLength(tmp.get(1));
		} else {
			// all already have at least one incident vertice, we could not remove any, so we'll calculate the min-spann tree
			// and we need to add another edge to make it to a circle (just random edge maybe?)
			for (Edge edge : graph.edges) {
				if(!includedEdges.contains(edge)) {
					result += graph.getLength(edge);
					break;
				}
			}
		}
		
		// find minimum spanning tree on the remaining graph
		List<Edge> mstEdges = kruskal.minimumSpanningTree(g, node);

		// sum up all edges from the minimum spanning tree
		for (Edge e : mstEdges) {
			result += graph.getLength(e);
		}
		
//		System.out.println(result);
		return result;
	}
	
	// for saving LP formulation into a file
	private static int fileNumber = 0;
	
	public static double zonesLB(BnBNode node, final Graph graph) {
		double result = 0;
		
		// get all excluded edges
		List<Edge> excludedEdges = getExcludedEdges(node);

        try {
        	// create an LP and set an objective function
        	LpSolve lp = LpSolve.makeLp(0, graph.getVertices());
        	double[] objCoefs = new double[graph.getVertices()];
        	int[] colno = new int[graph.getVertices()];
        	for (int i = 0; i < objCoefs.length; i++) {
				objCoefs[i] = 1;
				lp.setColName(i+1, "r"+i);
				colno[i] = i+1;
			}
        	lp.setObjFnex(graph.getVertices(), objCoefs, colno);
        	
//        	//add constraints
        	int[] col = new int[2];
        	double[] vars = {1.0, 1.0};
        	lp.setAddRowmode(true);
        	for (Edge edge : graph.edges) {
				if (!excludedEdges.contains(edge)) {
					col[0] = edge.u+1;
					col[1] = edge.v+1;
					lp.addConstraintex(2, vars, col, LpSolve.LE, graph.getLength(edge));
				}
			}
        	lp.setAddRowmode(false);
        	
        	//we want to maximize that shit
        	lp.setMaxim();
        	
        	// save LP to a file for debugging
//        	lp.writeLp("model_" + fileNumber + ".lp");
//        	fileNumber++;
        	
        	//show only important messages
        	lp.setVerbose(LpSolve.IMPORTANT);
        	
        	int ret = lp.solve();
            if(ret != LpSolve.OPTIMAL) {
            	System.out.println("SOLUTION WAS NOT OPTIMAL, LOL");
            }
        	
        	result = 2.0 * lp.getObjective();
        	
        	lp.deleteLp();
		} catch (LpSolveException e) {
			e.printStackTrace();
		}
        
//        System.out.println(result);
		return result;
	}
	
	public static double integerRelaxationLB(BnBNode node, final Graph graph) {
		double result = 0;
		
		// get all excluded edges
		List<Edge> excludedEdges = getExcludedEdges(node);

		int uOffset = graph.edges.size();
		int varsLen = uOffset + graph.getVertices();
		int[][] varsMap = new int[graph.getVertices()][graph.getVertices()];
        try {
        	// create an LP and set an objective function
        	LpSolve lp = LpSolve.makeLp(0, varsLen);
        	double[] objCoefs = new double[uOffset];
        	int[] colno = new int[uOffset];
        	for (int i = 0; i < uOffset; i++) {
        		Edge e = graph.edges.get(i);
        		objCoefs[i] = graph.getLength(e);
				lp.setColName(i+1, "x_"+e.u+"_"+e.v);
				varsMap[e.u][e.v] = varsMap[e.v][e.u] = colno[i] = i+1;
			}
        	lp.setObjFnex(uOffset, objCoefs, colno);
        	for (int i = 0; i < graph.getVertices(); i++) {
        		lp.setColName(uOffset + i+1, "u_"+i);
			}
        	
        	//add constraints sum(x)=1        	
        	lp.setAddRowmode(true);
        	for (int i = 0; i < graph.getVertices(); i++) {
        		int incidentECount = graph.incidentEdges[i].size();
        		int[] col = new int[incidentECount];
            	double[] vars = new double[incidentECount];
            	int varCount = 0;
				for (int j = 0; j < incidentECount; j++) {
					Edge e = graph.incidentEdges[i].get(j);
					if(!excludedEdges.contains(e)) {
						vars[varCount] = 1;
						col[varCount] = varsMap[e.u][e.v];
						varCount++;
					}
				}
				lp.addConstraintex(varCount, vars, col, LpSolve.EQ, 2);
			}

        	for (Edge edge : graph.edges) {
        		// set upper bound for x variables
            	lp.setUpbo(varsMap[edge.u][edge.v], 1.0);
            	//subtour elimination constraints
				if (!excludedEdges.contains(edge) && edge.u != 0 && edge.v != 0) {
					int[] col = new int[3];
					col[0] = uOffset + edge.u + 1;
					col[1] = uOffset + edge.v + 1;
					col[2] = varsMap[edge.u][edge.v];
	            	double[] vars = {1.0, -1.0, graph.getVertices()};
	            	lp.addConstraintex(3, vars, col, LpSolve.LE, graph.getVertices()-1);
				}
			}
        	lp.setAddRowmode(false);
        	
        	//we want to maximize that shit
        	lp.setMinim();
        	
        	// save LP to a file for debugging
//        	lp.writeLp("model_" + fileNumber + ".lp");
//        	fileNumber++;
        	
        	//show only important messages
        	lp.setVerbose(LpSolve.IMPORTANT);
        	
        	int ret = lp.solve();
//            if(ret != LpSolve.OPTIMAL) {
//            	lp.writeLp("not_optimal.lp");
//            	System.out.println("SOLUTION WAS NOT OPTIMAL, LOL");
//            }
        	
        	result = lp.getObjective();
        	
        	lp.deleteLp();
		} catch (LpSolveException e) {
			e.printStackTrace();
		}
        
//        System.out.println(result);
		return result;
	}
	
	private static List<Edge> getExcludedEdges(BnBNode node) {
		List<Edge> excludedEdges = new ArrayList<Edge>();
		BnBNode n = node;
		while(n.parent!=null) {
			if(!n.edgeIncluded) {
				excludedEdges.add(n.edge);
			}
			n = n.parent;
		}
		return excludedEdges;
	}
	
}
